"""
dynamic programming
动态规划问题
nums = [1, 2, 4, 1, 7, 8, 3]
一组数据中 不能取连续数字 确保取出的数字和最大
"""
nums = [1, 2, 4, 1, 7, 8, 3]


def maxRecursion(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    else:
        return max(maxRecursion(n - 2) + nums[n], maxRecursion(n - 1))


def maxDp(nums):
    opts = [0 for _ in nums]
    opts[0] = nums[0]
    opts[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        opts[i] = max(opts[i-2]+nums[i], opts[i-1])
    return opts[-1]


print(maxRecursion(len(nums) - 1))
print(maxDp(nums))
